import java.util.*;

public class SortingAlgorithms {

    // 主函数
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); // 创建 Scanner 对象用于用户输入

        // 提示用户选择输入方式
        System.out.println("请选择输入方式：1. 手动输入 2. 随机生成");
        int choice = scanner.nextInt(); // 读取用户的选择

        int[] array; // 定义数组用于存储排序序列
        if (choice == 1) {
            // 手动输入序列
            System.out.println("请输入序列长度：");
            int length = scanner.nextInt(); // 读取序列长度
            array = new int[length]; // 初始化数组
            System.out.println("请输入不重复的数字序列：");
            for (int i = 0; i < length; i++) {
                array[i] = scanner.nextInt(); // 读取用户输入的每个数字
            }
        } else {
            // 随机生成序列
            System.out.println("请输入序列长度：");
            int length = scanner.nextInt(); // 读取序列长度
            array = generateRandomArray(length); // 调用生成随机数组的方法
        }

        // 打印原始序列
        System.out.println("原始序列：" + Arrays.toString(array));

        // 提示用户选择排序方法
        System.out.println("请选择排序方法（输入序号，多个序号用空格分隔）：");
        System.out.println("1. 直接插入排序 2. 冒泡排序 3. 希尔排序 4. 快速排序 5. 基数排序 6. 归并排序 7. 选择排序 8. TimSort");
        scanner.nextLine(); // 清除缓冲区
        String[] selections = scanner.nextLine().split(" "); // 读取用户选择的排序方法

        // 根据用户选择执行相应的排序算法
        for (String selection : selections) {
            int[] sortedArray = array.clone(); // 克隆原始数组以避免修改原始数据
            switch (selection) {
                case "1":
                    System.out.println("\n=== 直接插入排序 ===");
                    insertionSort(sortedArray); // 调用直接插入排序
                    break;
                case "2":
                    System.out.println("\n=== 冒泡排序 ===");
                    bubbleSort(sortedArray); // 调用冒泡排序
                    break;
                case "3":
                    System.out.println("\n=== 希尔排序 ===");
                    shellSort(sortedArray); // 调用希尔排序
                    break;
                case "4":
                    System.out.println("\n=== 快速排序 ===");
                    quickSort(sortedArray, 0, sortedArray.length - 1); // 调用快速排序
                    break;
                case "5":
                    System.out.println("\n=== 基数排序 ===");
                    radixSort(sortedArray); // 调用基数排序
                    break;
                case "6":
                    System.out.println("\n=== 归并排序 ===");
                    mergeSort(sortedArray, 0, sortedArray.length - 1); // 调用归并排序
                    break;
                case "7":
                    System.out.println("\n=== 选择排序 ===");
                    selectionSort(sortedArray); // 调用选择排序
                    break;
                case "8":
                    System.out.println("\n=== TimSort ===");
                    timSort(sortedArray); // 调用 TimSort
                    break;
                default:
                    System.out.println("无效的选择：" + selection); // 处理无效输入
            }
        }
    }

    // 生成不重复的随机数组
    private static int[] generateRandomArray(int length) {
        Set<Integer> set = new HashSet<>(); // 使用 Set 确保数字不重复
        Random random = new Random(); // 创建 Random 对象用于生成随机数
        while (set.size() < length) {
            set.add(random.nextInt(10002
            )); // 生成 0 到 99 之间的随机数并添加到 Set
        }
        int[] array = new int[length]; // 初始化数组
        int index = 0;
        for (int num : set) {
            array[index++] = num; // 将 Set 中的数字复制到数组
        }
        return array; // 返回生成的数组
    }

    // 直接插入排序
    private static void insertionSort(int[] array) {
        for (int i = 1; i < array.length; i++) { // 从第二个元素开始遍历
            int key = array[i]; // 当前需要插入的元素
            int j = i - 1; // 从当前元素的前一个元素开始比较
            while (j >= 0 && array[j] > key) { // 如果前一个元素比当前元素大
                array[j + 1] = array[j]; // 将前一个元素后移
                j--; // 继续向前比较
            }
            array[j + 1] = key; // 插入当前元素到正确位置
            System.out.println("第 " + i + " 次插入后：" + Arrays.toString(array)); // 打印当前数组状态
        }
    }

    // 冒泡排序
    private static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) { // 外层循环控制轮数
            for (int j = 0; j < array.length - 1 - i; j++) { // 内层循环进行比较
                if (array[j] > array[j + 1]) { // 如果前一个元素比后一个元素大
                    int temp = array[j]; // 交换两个元素
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
            System.out.println("第 " + (i + 1) + " 轮冒泡后：" + Arrays.toString(array)); // 打印当前数组状态
        }
    }

    // 希尔排序
    private static void shellSort(int[] array) {
        int gap = array.length / 2; // 初始间隔为数组长度的一半
        while (gap > 0) { // 当间隔大于 0 时继续排序
            for (int i = gap; i < array.length; i++) { // 从间隔位置开始遍历
                int temp = array[i]; // 当前需要插入的元素
                int j = i;
                while (j >= gap && array[j - gap] > temp) { // 如果前一个元素比当前元素大
                    array[j] = array[j - gap]; // 将前一个元素后移
                    j -= gap; // 继续向前比较
                }
                array[j] = temp; // 插入当前元素到正确位置
            }
            System.out.println("间隔为 " + gap + " 的排序后：" + Arrays.toString(array)); // 打印当前数组状态
            gap /= 2; // 缩小间隔
        }
    }

    // 快速排序
    private static void quickSort(int[] array, int low, int high) {
        if (low < high) { // 如果子数组长度大于 1
            int pi = partition(array, low, high); // 获取分区点
            System.out.println("分区后：" + Arrays.toString(array)); // 打印当前数组状态
            quickSort(array, low, pi - 1); // 对左子数组递归排序
            quickSort(array, pi + 1, high); // 对右子数组递归排序
        }
    }

    // 快速排序的分区函数
    private static int partition(int[] array, int low, int high) {
        int pivot = array[high]; // 选择最后一个元素作为基准
        int i = low - 1; // i 是较小元素的索引
        for (int j = low; j < high; j++) { // 遍历数组
            if (array[j] < pivot) { // 如果当前元素小于基准
                i++; // 增加较小元素的索引
                int temp = array[i]; // 交换 array[i] 和 array[j]
                array[i] = array[j];
                array[j] = temp;
            }
        }
        int temp = array[i + 1]; // 将基准元素放到正确位置
        array[i + 1] = array[high];
        array[high] = temp;
        return i + 1; // 返回分区点
    }

    // 基数排序
    private static void radixSort(int[] array) {
        int max = Arrays.stream(array).max().getAsInt(); // 获取数组中的最大值
        for (int exp = 1; max / exp > 0; exp *= 10) { // 按位数进行排序
            countingSort(array, exp); // 调用计数排序
            System.out.println("按位数 " + exp + " 排序后：" + Arrays.toString(array)); // 打印当前数组状态
        }
    }

    // 基数排序的计数排序辅助函数
    private static void countingSort(int[] array, int exp) {
        int[] output = new int[array.length]; // 输出数组
        int[] count = new int[10]; // 计数数组

        for (int i = 0; i < array.length; i++) { // 统计每个数字的出现次数
            count[(array[i] / exp) % 10]++;
        }

        for (int i = 1; i < 10; i++) { // 计算累加次数
            count[i] += count[i - 1];
        }

        for (int i = array.length - 1; i >= 0; i--) { // 将元素放入输出数组
            output[count[(array[i] / exp) % 10] - 1] = array[i];
            count[(array[i] / exp) % 10]--;
        }

        System.arraycopy(output, 0, array, 0, array.length); // 将输出数组复制回原数组
    }

    // 归并排序
    private static void mergeSort(int[] array, int left, int right) {
        if (left < right) { // 如果子数组长度大于 1
            int mid = (left + right) / 2; // 计算中间位置
            mergeSort(array, left, mid); // 对左子数组递归排序
            mergeSort(array, mid + 1, right); // 对右子数组递归排序
            merge(array, left, mid, right); // 合并两个子数组
            System.out.println("合并后：" + Arrays.toString(array)); // 打印当前数组状态
        }
    }

    // 归并排序的合并函数
    private static void merge(int[] array, int left, int mid, int right) {
        int[] temp = new int[right - left + 1]; // 临时数组
        int i = left, j = mid + 1, k = 0; // i 和 j 分别是左右子数组的起始索引，k 是临时数组的索引

        while (i <= mid && j <= right) { // 合并两个子数组
            if (array[i] <= array[j]) {
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }

        while (i <= mid) { // 将左子数组剩余元素复制到临时数组
            temp[k++] = array[i++];
        }

        while (j <= right) { // 将右子数组剩余元素复制到临时数组
            temp[k++] = array[j++];
        }

        System.arraycopy(temp, 0, array, left, temp.length); // 将临时数组复制回原数组
    }

    // 选择排序
    private static void selectionSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) { // 外层循环控制轮数
            int minIndex = i; // 假设当前元素是最小值
            for (int j = i + 1; j < array.length; j++) { // 内层循环查找最小值
                if (array[j] < array[minIndex]) {
                    minIndex = j; // 更新最小值索引
                }
            }
            int temp = array[minIndex]; // 交换当前元素和最小值
            array[minIndex] = array[i];
            array[i] = temp;
            System.out.println("第 " + (i + 1) + " 次选择后：" + Arrays.toString(array)); // 打印当前数组状态
        }
    }

    // TimSort
    private static void timSort(int[] array) {
        int minRun = 32; // TimSort 的最小运行长度
        int n = array.length; // 数组长度

        // 对每个 run 进行插入排序
        for (int i = 0; i < n; i += minRun) {
            insertionSort(array, i, Math.min(i + minRun - 1, n - 1)); // 调用插入排序
        }

        // 合并 run
        for (int size = minRun; size < n; size = 2 * size) { // 逐步增加 run 的大小
            for (int left = 0; left < n; left += 2 * size) { // 遍历数组
                int mid = left + size - 1; // 计算中间位置
                int right = Math.min(left + 2 * size - 1, n - 1); // 计算右边界
                if (mid < right) { // 如果存在两个 run
                    merge(array, left, mid, right); // 合并两个 run
                    System.out.println("合并 run 后：" + Arrays.toString(array)); // 打印当前数组状态
                }
            }
        }
    }

    // 插入排序（用于 TimSort）
    private static void insertionSort(int[] array, int left, int right) {
        for (int i = left + 1; i <= right; i++) { // 从第二个元素开始遍历
            int key = array[i]; // 当前需要插入的元素
            int j = i - 1; // 从当前元素的前一个元素开始比较
            while (j >= left && array[j] > key) { // 如果前一个元素比当前元素大
                array[j + 1] = array[j]; // 将前一个元素后移
                j--; // 继续向前比较
            }
            array[j + 1] = key; // 插入当前元素到正确位置
        }
    }
}